package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
 * <p>
 * 39. 组合总和
 * https://leetcode-cn.com/problems/combination-sum/
 */
public class $4月21日$组合总和 {


 List<List<Integer>> res = new ArrayList();
   int[] arr;
   int target;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.arr = candidates;
        this.target= target;
        Arrays.sort(arr);
        backtrack(0,0);
        return res;
    }

    List<Integer> cur = new ArrayList();
  
    public void backtrack(int index,int sum){
         if(sum==target){
             res.add(new ArrayList(cur));
             return;
         }

         for(int i= index;i<arr.length;i++){
             if(sum+arr[i]<=target){
                 cur.add(arr[i]);
                 backtrack(i,sum+arr[i]);
                cur.remove(cur.size()-1);
             }
            
         }
    }
}
